/**
 * 贪心-最少硬币找零问题：给出要找零的钱数，以及一些面额和对应限制数量，
 * 问哪种找零方法所需硬币个数最少。
 * @param coins 面额数组（单纯的面额，这里没有限制数量）
 * @param amount 找零的目标值（要找零的钱数）
 * 例如：美元的硬币面额：1, 5, 10, 25 （单位：分）
 * 要找零36分，先找最大的面额25，再找剩余面额最大的10，最后只能找1
 */
export function minCoinChange(coins: number[], amount: number) {
    const change: number[] = [];
    let total = 0;
    for (let i = coins.length; i >= 0; i--) {
        const coin = coins[i];
        // 面额最大但总和不能超过amount
        while (total + coin <= amount) {
            change.push(coin);
            total += coin;
        }
    }
    return change;
}
